package class01;

import java.util.Arrays;

public class Code01_CordCoverMaxPoint {

	/**
	 * 使用二分查找方法计算绳子最多能覆盖的点数
	 * 思路：枚举每个点作为绳子右端点，通过二分查找找到绳子左端点最远能覆盖到的点
	 * 
	 * @param arr 输入的有序点数组
	 * @param L 绳子的长度
	 * @return 绳子最多能覆盖的点数量
	 */
	public static int maxPoint1(int[] arr, int L) {
		int res = 1;
		// 遍历每个点作为绳子的右端点
		for (int i = 0; i < arr.length; i++) {
			// 通过二分查找找到绳子左端点最远能覆盖到的点的索引
			int nearest = nearestIndex(arr, i, arr[i] - L);
			// 更新最大覆盖点数
			res = Math.max(res, i - nearest + 1);
		}
		return res;
	}

	/**
	 * 在有序数组中查找大于等于value的最左边的元素索引（二分查找）
	 * 
	 * @param arr 有序数组
	 * @param R 搜索的右边界
	 * @param value 目标值
	 * @return 大于等于value的最左边元素的索引
	 */
	public static int nearestIndex(int[] arr, int R, int value) {
		int L = 0;
		int index = R;
		// 二分查找过程
		while (L <= R) {
			int mid = L + ((R - L) >> 1);
			// 如果中间元素大于等于目标值，则记录该位置，并向左继续查找
			if (arr[mid] >= value) {
				index = mid;
				R = mid - 1;
			} else {
				// 如果中间元素小于目标值，则向右继续查找
				L = mid + 1;
			}
		}
		return index;
	}

	/**
	 * 使用滑动窗口方法计算绳子最多能覆盖的点数
	 * 思路：使用双指针维护一个滑动窗口，窗口内的点都能被绳子覆盖
	 * 
	 * @param arr 输入的有序点数组
	 * @param L 绳子的长度
	 * @return 绳子最多能覆盖的点数量
	 */
	public static int maxPoint2(int[] arr, int L) {
		int left = 0;
		int right = 0;
		int N = arr.length;
		int max = 0;
		// 滑动窗口过程
		while (left < N) {
			// 扩展右边界，直到窗口无法被绳子覆盖
			while (right < N && arr[right] - arr[left] <= L) {
				right++;
			}
			// 更新最大覆盖点数
			max = Math.max(max, right - (left++));
		}
		return max;
	}

	// for test
	public static int test(int[] arr, int L) {
		int max = 0;
		for (int i = 0; i < arr.length; i++) {
			int pre = i - 1;
			while (pre >= 0 && arr[i] - arr[pre] <= L) {
				pre--;
			}
			max = Math.max(max, i - pre);
		}
		return max;
	}

	// for test
	public static int[] generateArray(int len, int max) {
		int[] ans = new int[(int) (Math.random() * len) + 1];
		for (int i = 0; i < ans.length; i++) {
			ans[i] = (int) (Math.random() * max);
		}
		Arrays.sort(ans);
		return ans;
	}

	public static void main(String[] args) {
		int len = 100;
		int max = 1000;
		int testTime = 100000;
		System.out.println("测试开始");
		for (int i = 0; i < testTime; i++) {
			int L = (int) (Math.random() * max);
			int[] arr = generateArray(len, max);
			int ans1 = maxPoint1(arr, L);
			int ans2 = maxPoint2(arr, L);
			int ans3 = test(arr, L);
			if (ans1 != ans2 || ans2 != ans3) {
				System.out.println("oops!");
				break;
			}
		}

	}

}